#ifndef SLAKS_SORTED_GRAPH
#define SLAKS_SORTED_GRAPH

#include <boost/graph/adjacency_list.hpp>

#include <list>
#include <vector>
#include <algorithm>

namespace slaks {
	namespace graphs {

		typedef boost::vecS vecS;
		typedef boost::listS listS;
		typedef boost::directedS directedS;

		template <typename OutEdgeListS = vecS,
			typename VertexListS = vecS,
			typename DirectedS = directedS,
			typename VertexProperty = boost::no_property,
			typename EdgeProperty = boost::no_property,
			typename GraphProperty = boost::no_property
		>
		class sortable_graph : public boost::adjacency_list<OutEdgeListS,VertexListS,DirectedS,VertexProperty,EdgeProperty,GraphProperty>{
			public:
				typedef boost::adjacency_list<OutEdgeListS,
				                            VertexListS,
																		DirectedS,
																		VertexProperty,
																		EdgeProperty,
																		GraphProperty
																	 > base_graph_t;
			
				typedef typename boost::graph_traits<base_graph_t>::vertex_descriptor vertex_descriptor;
				typedef typename std::vector<vertex_descriptor> list_t;
				typedef typename list_t::iterator vertex_iterator;
				typedef typename list_t::size_type vertices_size_type;

				list_t vertex_list;

		};//end of class sortable_graph

		//return first and last iterator of the sortbale list of vertices
		template <typename OutEdgeListS,
			typename VertexListS,
			typename DirectedS,
			typename VertexProperty,
			typename EdgeProperty,
			typename GraphProperty>
		std::pair<typename sortable_graph<OutEdgeListS,VertexListS,DirectedS,VertexProperty,EdgeProperty,GraphProperty>::vertex_iterator,
		          typename sortable_graph<OutEdgeListS,VertexListS,DirectedS,VertexProperty,EdgeProperty,GraphProperty>::vertex_iterator > vertices(sortable_graph<OutEdgeListS,VertexListS,DirectedS,VertexProperty,EdgeProperty,GraphProperty> &graph)
		{
			return std::make_pair(graph.vertex_list.begin(),graph.vertex_list.end());
		}

		template <typename GraphType, typename PropertyType>
		 struct NodeSort {
			 typedef typename GraphType::vertex_descriptor vertex_t;
			  NodeSort(PropertyType &property) : property(property) { }
				bool operator()(vertex_t vertex1,vertex_t vertex2) {
					 return boost::get(property,vertex1) < boost::get(property,vertex2);
				}
			 PropertyType &property;
		};
	
	  template <typename VertexType, typename Map, typename Key>
		typename VertexType * get_vertex(const Key &key, Map & map)
		{
			Map::iterator iter = map.find(key);
			if (iter == map.end()) return NULL;
			return &(iter->second);
		}

		template <typename GraphType,typename PropertyType,typename BundleClass, typename BundleMemberType>
    typename GraphType * set_intersection(typename GraphType::vertex_iterator &iter_start_graph1,
																			typename GraphType::vertex_iterator &iter_end_graph1,
																			typename GraphType::vertex_iterator &iter_start_graph2,
																			typename GraphType::vertex_iterator &iter_end_graph2,
																			PropertyType &property_graph1,
																			PropertyType &property_graph2,
																			BundleMemberType BundleClass::*mem
																			) {
				GraphType *graph = new GraphType;
				typedef boost::property_traits<PropertyType>::value_type property_value_t;
				typedef typename GraphType::vertex_descriptor vertex_t;

				vertex_t vertex;

				property_value_t value;
				property_value_t value2;

				for (;iter_start_graph1 != iter_end_graph1,iter_start_graph2 != iter_end_graph2;)
				{
					value = property_graph1[*iter_start_graph1];
					value2 = property_graph2[*iter_start_graph2];
					if (value < value2) ++iter_start_graph1;
					else if (value == value2)
					{
						vertex = add_vertex(*graph);
						graph->vertex_list.push_back(vertex);

						boost::put(mem,*graph,vertex,value);

						++iter_start_graph1;
						++iter_start_graph2;
					}
					else ++iter_start_graph2;
				}

				return graph;
    } 

	template <typename GraphType,typename BundleVertexClass, typename BundleVertexMemberType, typename BundleEdgeClass, typename BundleEdgeMemberType>
    typename GraphType * set_intersection2(GraphType &graph1, 
		                                       GraphType &graph2,
																			     BundleVertexMemberType BundleVertexClass::*vertex_property_pointer,
																					 BundleEdgeMemberType BundleEdgeClass::*edge_property_pointer
																			) {
				GraphType *graph = new GraphType;

				typedef typename boost::property_map<GraphType::base_graph_t,BundleVertexMemberType BundleVertexClass::* >::type VertexPropertyType;
				typedef typename boost::property_traits<VertexPropertyType>::value_type vertex_property_value_t;
				typedef typename GraphType::vertex_descriptor vertex_t;
				typedef typename boost::graph_traits<graph_t::base_graph_t>::vertex_iterator vertex_iter_t;
				typedef typename graph_t::vertex_descriptor vertex_descriptor;

				typedef typename boost::property_map<GraphType::base_graph_t,BundleEdgeMemberType BundleEdgeClass::* >::type EdgePropertyType;
				typedef typename boost::property_traits<EdgePropertyType>::value_type edge_property_value_t;
				typedef typename GraphType::base_graph_t::edge_descriptor edge_t;
				typedef typename boost::graph_traits<graph_t::base_graph_t>::out_edge_iterator edge_iter_t;


				//store the original vertices that are equal in both graphs for further iteration and equal edge search
				typedef std::list<vertex_descriptor> vertex_list_t;
				vertex_list_t temp_vertex_list1,temp_vertex_list2;

				vertex_iter_t iter_start_graph1,iter_end_graph1,iter_start_graph2,iter_end_graph2;

				//get vertex iterators
				boost::tie(iter_start_graph1,iter_end_graph1) = boost::vertices(graph1);
				boost::tie(iter_start_graph2,iter_end_graph2) = boost::vertices(graph2);

				//get the vertex properties of the graphs
				VertexPropertyType property_graph1 = boost::get(vertex_property_pointer,graph1);
				VertexPropertyType property_graph2 = boost::get(vertex_property_pointer,graph2);

				vertex_t vertex;

				vertex_property_value_t value;
				vertex_property_value_t value2;

				//iterate through vertices of the graph 
				for (;iter_start_graph1 != iter_end_graph1,iter_start_graph2 != iter_end_graph2;)
				{
					value = property_graph1[*iter_start_graph1];
					value2 = property_graph2[*iter_start_graph2];
					if (value < value2) ++iter_start_graph1;
					else if (value == value2)
					{
						vertex = add_vertex(*graph);
						graph->vertex_list.push_back(vertex);
						temp_vertex_list1.push_back(*iter_start_graph1); //store vertex of the graph1
						temp_vertex_list2.push_back(*iter_start_graph2); //store vertex of the graph2

						boost::put(vertex_property_pointer,*graph,vertex,value);

						++iter_start_graph1;
						++iter_start_graph2;
					}
					else ++iter_start_graph2;
				}//end of for

				if (temp_vertex_list1.size() == 1) return graph;

				//now we must find all the equal edges between nodes in the intersection set with equal edge labels in both graphs
				vertex_list_t::iterator vert_iter_start_graph1 = temp_vertex_list1.begin();
				vertex_list_t::iterator vert_iter_end_graph1 = temp_vertex_list1.end();

				vertex_list_t::iterator vert_iter_start_graph2 = temp_vertex_list2.begin();
				vertex_list_t::iterator vert_iter_end_graph2 = temp_vertex_list2.end();
				
				graph_t::vertex_iterator vert_iter_start_graph3 = graph1.vertex_list.begin();
				graph_t::vertex_iterator vert_iter_end_graph3 = graph1.vertex_list.end();

				vertex_t vertex_left1,vertex_right1,vertex_left2,vertex_right2,vertex_left3,vertex_right3;

				//assign first vertex and increment the iterators
				vertex_left1 = *vert_iter_start_graph1++;
				vertex_left2 = *vert_iter_start_graph2++;
				vertex_left3 = *vert_iter_start_graph3++;

				edge_iter_t edge_iter_start_graph1,edge_iter_end_graph1,edge_iter_start_graph2,edge_iter_end_graph2;
				edge_property_value_t edge_value1,edge_value2;

				for (;vert_iter_start_graph1 != vert_iter_end_graph1;)
				{
					vertex_right1 = *vert_iter_start_graph1;
					vertex_right2 = *vert_iter_start_graph2;
					vertex_right3 = *vert_iter_start_graph3;

					boost::tie(edge_iter_start_graph1,edge_iter_end_graph1) = boost::out_edges(vertex_left1,graph1);

					for (; edge_iter_start_graph1 != edge_iter_end_graph1 ; )
					{
						if (target(*edge_iter_start_graph1,graph1) != vertex_right1) continue;
						//found edge which connectes left vertex 1 to right vertex 1
					}
				}


				return graph;
    } 

	}//namespace graph
}//namespace slaks

#endif